﻿<?xml version="1.0" encoding="utf-8"?><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html>
<!-- saved from url=(0033)http://research.microsoft.com/pex -->
<head><link rel="StyleSheet" href="er.common.css" type="text/css" /><script src="er.common.js" type="text/javascript"> </script><link rel="SHORTCUT ICON" href="favicon.ico" /><link rel="icon" href="favicon.ico" type="image/x-icon" /><title>C:\Users\AO\Documents\Visual Studio 2010\AutomaTones3\automatones\AutomaTones\AutomaTones\Model\Automaton Model\Cellular Automaton.cs</title></head><body><div class="banner"></div><h2 id="top">C:\Users\AO\Documents\Visual Studio 2010\AutomaTones3\automatones\AutomaTones\AutomaTones\Model\Automaton Model\Cellular Automaton.cs</h2><div class="toggle"><p class="copyright"><a class="usercodeundertestcovered">user code under test</a>, 
  <span class="usercodeundertestnotcovered">user code under test (not covered)</span>, 
  <a class="userortestcodecovered">user code or test</a>, 
  <span class="userortestcodenotcovered">user code or test (not covered)</span>,
  <span class="tagged">tagged</span></p><table><tr><th>Methods</th></tr><tr><th /></tr></table><div class="toggle"><a class="button" href="#ID0EL">first</a><pre class="coverage">using System;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
using Microsoft.Pex.Framework;

namespace AutomaTones.Model.Automaton_Model {
    /// &lt;summary&gt;
    ///   A cellular automaton consisting of an N-dimensional grid of cells.
    ///   Every new generation each cell gets a given state defined by one or more rules.
    ///   These rules consider a predefined set of neighbouring cells and hence decide a cells new state.
    ///   States are always represented using integers (discrete values).
    ///   States can be set and read via an indexer, eg. ca[0, 1] = 1;&lt;br&gt;&lt;/br&gt;&lt;br&gt;&lt;/br&gt;
    ///   NOTE: Ideally this would be implemented using generics so states could also be decimals.
    ///   But due to C#'s lack of type constraint options on value types - this was omitted.&lt;br&gt;&lt;/br&gt;&lt;br&gt;&lt;/br&gt;
    ///   This implementation is designed to allow a high degree of flexibility in the use of cellular automata.
    ///   Its N-dimensional and each cell may have its own state space and rule(s). Rules can use different
    ///   neighbourhoods which they process with their RuleDelegate - which again may use other delegates.
    ///   Thus this flexibility may make the overall semantics a little confusing at first.
    ///   However, one can setup a simple CA where all cells use the same space, rule and neighbourhood 
    ///   by simply using one of the constructors.
    /// &lt;/summary&gt;
    /// &lt;author&gt;Anders Øland / anoe@itu.dk&lt;/author&gt;
    [PexClass]
    [Serializable]
    public class CellularAutomaton : ICloneable {
        public uint Dimensions { get; private set; }
        public uint DimensionSize { get; private set; }
        public uint Generation { get; private set; }

        // _grid hold the cells of CA's the N-dimensional grid
        protected Cell[] Grid;

        public Rule DefaultRule { get; private set; }

        /// &lt;summary&gt;
        ///   Construct a new Cellular Automaton
        /// &lt;/summary&gt;
        /// &lt;param name = "dimensions"&gt;Number of dimensions&lt;/param&gt;
        /// &lt;param name = "dimensionSize"&gt;Size of the dimensions&lt;/param&gt;
        /// &lt;param name = "defaultRule"&gt;The default rule for all cells&lt;/param&gt;
        /// &lt;param name = "stateMin"&gt;default = 0&lt;/param&gt;
        /// &lt;param name = "stateMax"&gt;default = 1&lt;/param&gt;
        /// &lt;param name = "stateInit"&gt;&lt;/param&gt;
//        [PexMethod]
        <span id="ID0EL"><a class="button" href="#top">top</a>|<a class="button" href="#ID0EED">next</a></span><a class="userortestcodecovered">public CellularAutomaton(uint dimensions, uint dimensionSize, Rule defaultRule, int stateMin = 0,
                                 int stateMax = 1, int stateInit = 0)</a> <a class="userortestcodecovered">{</a>
            Contract.Requires(0 &lt; dimensions);
            Contract.Requires(0 &lt; dimensionSize);
            Contract.Requires(null != defaultRule);
            Contract.Requires(dimensions == defaultRule.Dimensions);
            Contract.Requires(stateMin &lt; stateMax);
            Contract.Requires(stateMin &lt;= stateInit &amp;&amp; stateMax &gt;= stateInit);
            <a class="userortestcodecovered">Init(dimensions, dimensionSize, defaultRule, stateMin, stateMax, stateInit);</a>
        <a class="userortestcodecovered">}</a>

        private void Init(uint dimensions, uint dimensionSize, Rule defaultRule,
                          int stateMin = 0, int stateMax = 1, int stateInit = 0) <a class="button" href="#ID0EL">prev</a>|<span id="ID0EED"><a class="button" href="#top">top</a>|<a class="button" href="#ID0E6EAC">next</a></span><a class="userortestcodecovered">{</a>
            Contract.Requires(0 &lt; dimensions &amp;&amp; 0 &lt; dimensionSize);
            Contract.Requires(dimensions == defaultRule.Dimensions);
            Contract.Requires(stateMin &lt; stateMax);
            Contract.Requires(stateMin &lt;= stateInit &amp;&amp; stateMax &gt;= stateInit);
            <a class="userortestcodecovered">Generation = 0;</a>
            <a class="userortestcodecovered">Dimensions = dimensions;</a>
            <a class="userortestcodecovered">DimensionSize = dimensionSize;</a>
            <a class="tagged" title="call to external method Math.Pow(Double, Double)">Grid = new Cell[(int)Math.Pow(DimensionSize, Dimensions)];</a>
            for (<a class="userortestcodecovered">int i = 0;</a> <a class="userortestcodecovered">i &lt; Grid.Length</a>; <a class="userortestcodecovered">i++</a>) <a class="userortestcodecovered">{</a>
                <a class="userortestcodecovered">Grid[i] = new Cell(defaultRule, stateMin, stateMax, stateInit);</a>
            <a class="userortestcodecovered">}</a>
            <a class="userortestcodecovered">DefaultRule = defaultRule;</a>
        <a class="userortestcodecovered">}</a>

        /// &lt;summary&gt;
        ///   Finds the right cell in the N-dimensional grid in the one dimensional array holding the cells
        /// &lt;/summary&gt;
        [PexMethod]
        [Pure] // Tagged as pure since its being called from other contracts which I dont want to loosen 
        protected internal virtual Cell GetCell(params int[] coord) <a class="button" href="#ID0EL">prev</a>|<span id="ID0E6EAC"><a class="button" href="#top">top</a>|<a class="button" href="#ID0E3HAC">next</a></span><a class="userortestcodecovered">{</a>
            Contract.Requires(null != coord);
            Contract.Requires(coord.Length == Dimensions);
            Contract.Ensures(Contract.Result&lt;Cell&gt;() != null);
            <a class="userortestcodecovered">uint index = GetIndex(coord);</a>
            <a class="userortestcodecovered">return Grid[index];</a>
        <a class="userortestcodecovered">}</a>

        /// &lt;summary&gt;
        ///   Translates a coordinate into an index number pointing to the corresponing location in the grid array.
        ///   Coordinates exceeding the bounds of the grid are 'wrapped around', 
        ///   thus giving the grid a so-called torus shape.
        /// &lt;/summary&gt;
        [Pure]
        protected uint GetIndex(int[] coord) <a class="button" href="#ID0EL">prev</a>|<span id="ID0E3HAC"><a class="button" href="#top">top</a>|<a class="button" href="#ID0E6AAE">next</a></span><a class="userortestcodecovered">{</a>
            Contract.Requires(null != coord);
            Contract.Requires(0 &lt; DimensionSize &amp;&amp; 0 &lt; Dimensions);
            Contract.Requires(coord.Length == Dimensions);
            Contract.Ensures((uint)Math.Pow(DimensionSize, Dimensions) &gt; Contract.Result&lt;uint&gt;());
            <a class="userortestcodecovered">var index = 0;</a>
            for (<a class="userortestcodecovered">int i = 1;</a> <a class="userortestcodecovered">i &lt;= Dimensions</a>; <a class="userortestcodecovered">i++</a>) <a class="userortestcodecovered">{</a>
                // Loop invariant
                <a class="userortestcodecovered">Contract.Assert(0 &lt;= index &amp;&amp; Grid.Length &gt; index);</a>
                // Make sure coordinates which exceed the bounds of any dimension are 'wrapped around'
                <a class="userortestcodecovered">int c = coord[i - 1] % (int)DimensionSize;</a>
                <a class="userortestcodecovered">c = 0 &lt;= c ? c : c + (int)DimensionSize;</a>
                // Sum the the effect of each coordinate to find the correct position in the grid array
                <a class="userortestcodecovered">index += c * (int)Math.Pow(DimensionSize, Dimensions - i);</a>
            <a class="userortestcodecovered">}</a>
            <a class="userortestcodecovered">return (uint)index;</a>
        <a class="userortestcodecovered">}</a>

        /// &lt;summary&gt;
        ///   Translates an index number into a coordinate.
        /// &lt;/summary&gt;
        /// &lt;param name = "index"&gt;&lt;/param&gt;
        /// &lt;returns&gt;&lt;/returns&gt;
        private int[] GetCoordinate(uint index) <a class="button" href="#ID0EL">prev</a>|<span id="ID0E6AAE"><a class="button" href="#top">top</a>|<a class="button" href="#ID0EDEAE">next</a></span><a class="userortestcodecovered">{</a>
            Contract.Requires(index &lt; Grid.Length);
            Contract.Ensures(Dimensions == Contract.Result&lt;int[]&gt;().Length);
            // As long as the grid is rectangular (not jagged) this is equivalent to converting
            // index from base 10 to base DimensionSize.
            <a class="userortestcodecovered">return Tools.Math.DecimalToBase(index, DimensionSize, Dimensions).Reverse().ToArray();</a>
        <a class="userortestcodecovered">}</a>

        /// &lt;summary&gt;
        ///   Returns the State Object of the cell.
        /// &lt;/summary&gt;
        /// &lt;param name = "coord"&gt;&lt;/param&gt;
        /// &lt;returns&gt;The state of the cell with the given coordinates&lt;/returns&gt;
        public State GetCellState(params int[] coord) {
            Contract.Requires(coord.Length == Dimensions);
            Contract.Ensures(Contract.Result&lt;State&gt;() != null);
            return GetCell(coord).State;
        }

        /// &lt;summary&gt;
        ///   Returns the rule of the cell with the given coordinates.
        ///   Note that one rule may consist of many rules.
        /// &lt;/summary&gt;
        /// &lt;param name = "coord"&gt;Coordinates&lt;/param&gt;
        /// &lt;returns&gt;IRule&lt;/returns&gt;
        [PexMethod]
        public Rule GetCellRule(params int[] coord) {
            Contract.Requires(coord.Length == Dimensions);
            Contract.Ensures(Contract.Result&lt;Rule&gt;() != null);
            return GetCell(coord).Rule;
        }

        /// &lt;summary&gt;
        ///   Sets the rule of the cell with the given coordinates.
        /// &lt;/summary&gt;
        /// &lt;param name = "rule"&gt;&lt;/param&gt;
        /// &lt;param name = "coord"&gt;Coordinates&lt;/param&gt;
        public void SetCellRule(Rule rule, params int[] coord) {
            Contract.Requires(coord.Length == Dimensions);
            Contract.Requires(rule != null);
            GetCell(coord).Rule = rule;
        }

        /// &lt;summary&gt;
        ///   Add a trigger to the cell with the given coordinates.
        /// &lt;/summary&gt;
        /// &lt;param name = "trigger"&gt;Trigger&lt;/param&gt;
        /// &lt;param name = "coord"&gt;int[]&lt;/param&gt;
        public void AddTrigger(Trigger trigger, params int[] coord) {
            Contract.Requires(coord.Length == Dimensions);
            Contract.Requires(trigger != null);
            Contract.Ensures(GetCell(coord).Triggers.Contains(trigger));
            GetCell(coord).Triggers.Add(trigger);
        }

        /// &lt;summary&gt;
        ///   Removes the trigger from the cell with the given coodinates.
        /// &lt;/summary&gt;
        /// &lt;param name = "trigger"&gt;Trigger&lt;/param&gt;
        /// &lt;param name = "coord"&gt;coordinates&lt;/param&gt;
        public void RemoveTrigger(Trigger trigger, params int[] coord) {
            Contract.Requires(coord.Length == Dimensions);
            Contract.Requires(trigger != null);
            Contract.Ensures(!GetCell(coord).Triggers.Contains(trigger));
            GetCell(coord).Triggers.Remove(trigger);
        }

        /// &lt;summary&gt;
        ///   Evolve this Cellular Automaton - move one generation forward
        ///   by applying the rule(s) to the cells.
        /// &lt;/summary&gt;
        public virtual void Evolve() <a class="button" href="#ID0EL">prev</a>|<span id="ID0EDEAE"><a class="button" href="#top">top</a>|<a class="button" href="#ID0EUQAE">next</a></span><a class="userortestcodecovered">{</a>
            Contract.Ensures(Generation == Contract.OldValue(Generation) + 1);
            Contract.Ensures(Contract.ForAll(0, Grid.Length,
                                             i =&gt; Grid[i].State.CurrentState == Grid[i].State.NextState));
            // Calculate new states from current states
            for (<a class="userortestcodecovered">uint index = 0;</a> <a class="userortestcodecovered">index &lt; Grid.Length</a>; <a class="userortestcodecovered">index++</a>)
                <a class="userortestcodecovered">Grid[index].State.NextState = Grid[index].Rule.ApplyRule(GetCoordinate(index), this);</a>

            // Commit new states
            <a class="userortestcodecovered">foreach</a> (<a class="userortestcodecovered">Cell cell</a> <a class="userortestcodecovered">in</a> <a class="userortestcodecovered">Grid</a>) <a class="userortestcodecovered">cell.State.CurrentState = cell.State.NextState;</a>
            <a class="userortestcodecovered">Generation++;</a>
        <a class="userortestcodecovered">}</a>

        /// &lt;summary&gt;
        ///   Indexer for the CA's grid of cells.
        /// &lt;/summary&gt;
        /// &lt;param name = "coord"&gt;coordinate&lt;/param&gt;
        /// &lt;returns&gt;Cell at the given coordinate&lt;/returns&gt;
        public virtual int this[params int[] coord] {
            get {
                Contract.Requires(coord.Length == Dimensions);
                return GetCell(coord).State.CurrentState;
            }
            set <a class="button" href="#ID0EL">prev</a>|<span id="ID0EUQAE"><a class="button" href="#top">top</a></span><a class="userortestcodecovered">{</a>
                Contract.Requires(coord.Length == Dimensions);
                Contract.Ensures(GetCell(coord).State.CurrentState.Equals(value));
                <a class="userortestcodecovered">Grid[GetIndex(coord)].State.CurrentState = value;</a>
            <a class="userortestcodecovered">}</a>
        }

        /// &lt;summary&gt;
        ///   For iterating over the entire grid.
        /// &lt;/summary&gt;
        /// &lt;returns&gt;&lt;/returns&gt;
        [Pure]
        public IEnumerable&lt;int&gt; GridEnumerator() {
            return Grid.Select(cell =&gt; cell.State.CurrentState);
        }

        /// &lt;summary&gt;
        /// Returns a copy of the cellular automatons current grid of cells.
        /// &lt;/summary&gt;
        /// &lt;returns&gt;&lt;/returns&gt;
        public Cell[] CopyOfGrid() {
            Contract.Ensures(Contract.ForAll(0, Grid.Length, i =&gt; Grid[i] == Contract.Result&lt;Cell[]&gt;()[i]));
            Cell[] copy = new Cell[Grid.Length];
            for (int i = 0; i &lt; Grid.Length; i++) {
                Cell c = Grid[i];
                copy[i] = new Cell(c.Rule, c.State.SpaceMin, c.State.SpaceMax, c.State.CurrentState);
            }
            return copy;
        }

        [ContractInvariantMethod]
        // ReSharper disable UnusedMember.Local
        private void ObjInvar() {
            // ReSharper restore UnusedMember.Local
            Contract.Invariant(0 &lt;= Generation);
            Contract.Invariant(0 &lt; DimensionSize);
            Contract.Invariant(0 &lt; Dimensions);
            Contract.Invariant(Grid.Length == (int)Math.Pow((double)DimensionSize, (double)Dimensions));
            Contract.Invariant(Contract.ForAll(Grid, c =&gt; null != c));
            Contract.Invariant(null != DefaultRule);
        }

        public override
            string ToString() {
            String s = "", t = "";
            foreach (int i in GridEnumerator()) {
                s += i;
                if (s.Length &lt; 1 * DimensionSize) continue;
                t += s + "\n";
                s = "";
            }
            return t;
        }

        public object Clone() {
            return new CellularAutomaton(Dimensions, DimensionSize, DefaultRule) {
                Generation = Generation,
                Grid = CopyOfGrid()
            };
        }
    }

    /// &lt;author&gt;Anders Øland / anoe@itu.dk&lt;/author&gt;
    /// &lt;summary&gt;
    /// A specialized Cellular Automaton for Wolfram one-dimensional automata.
    /// The grid does not have a torus shape (coordinates are not 'wrapper around'), instead the actual size of the grid is in fact
    /// larger than the specified size - so borderline cells can be processed.
    /// &lt;/summary&gt;
    public class WolframAutomaton : CellularAutomaton {
        public uint ViewedSize { get; private set; }
        private readonly Cell[,] _viewedGrid;

        /// &lt;summary&gt;
        /// Create a new WolframAutomaton.
        /// &lt;/summary&gt;
        /// &lt;param name="wolframRule"&gt;&lt;/param&gt;
        /// &lt;param name="stateSpace"&gt;size of the state space, 2 = binary&lt;/param&gt;
        /// &lt;param name="viewedSize"&gt;size of the rectangular grid displaying the CA&lt;/param&gt;
        /// &lt;param name="actualSize"&gt;actual size of the CA in memmory&lt;/param&gt;
        public WolframAutomaton(Rule wolframRule, int stateSpace, uint viewedSize = 64u, uint actualSize = 100u)
            : base(1, actualSize, wolframRule, 0, stateSpace - 1) {
            Contract.Requires(3 &lt;= viewedSize);
            Contract.Requires(viewedSize &lt;= actualSize);
            Contract.Requires(null != wolframRule);
            Contract.Requires(1 &lt; stateSpace);
            ViewedSize = viewedSize;
            _viewedGrid = new Cell[ViewedSize, ViewedSize];
            base.GetCell((int)(actualSize / 2)).State.CurrentState = 1;
            UpdateViewedGrid();
            for (int i = 0; i &lt; viewedSize; i++) Evolve();
        }

        /// &lt;summary&gt;
        ///   Returns a cell from the viewed two-dimensional grid.
        /// &lt;/summary&gt;
        protected internal new Cell GetCell(params int[] coord) {
            Contract.Requires(coord.Length == 2);
            Contract.Ensures(Contract.Result&lt;Cell&gt;() != null);
            return _viewedGrid[coord[0], coord[1]];
        }

        public override sealed void Evolve() {
            base.Evolve();
            UpdateViewedGrid();
        }

        private void UpdateViewedGrid() {
            Contract.Requires(ViewedSize &lt;= DimensionSize);
            Contract.Requires(null != _viewedGrid);
            Contract.Requires(null != Grid);
            for (int y = 0; y &lt; ViewedSize; y++) {
                // Shift left
                for (int x = 0; x &lt; ViewedSize - 1; x++) _viewedGrid[x, y] = _viewedGrid[x + 1, y];
                // Add new generation
                _viewedGrid[ViewedSize - 1, y] = base.GetCell((int)(ViewedSize / 2 - y + (int)DimensionSize / 2));
            }
        }
    }
}</pre></div></div><hr /><table width="100%"><tr><td valign="top"><span class="copyright">Copyright (c) Microsoft Corporation. All rights reserved.</span><br /><span class="button" onclick="copySourceToClipboard()">Copy full source to clipboard</span></td></tr></table><div id="debugdiv"> </div></body></html>